This invention relates generally to packet switched communication systems.
With reference to computing systems, memory refers to a place where the computing system holds information, such information able to be accessed and worked on as appropriate. Random Access Memory (RAM) can be used in a personal computer to temporarily store data that is currently being accessed or worked on. Read-only memory can be used for storage of information that does not change. A conventional memory structure includes a memory space of data that includes a plurality of entries, each identifiable by a specific location in the memory space. Each entry has a name (the address) that serves to locate the contents within the memory space.
An associative memory element, more commonly referred to as content addressable memory (CAM), includes a different structure. CAM element objects are selected based on their contents, not based on their location in the memory space. Each CAM element includes a key and associated data. Examples of associative memory elements include a hash table and set-associative table. A content addressable memory is searched (searching of the keys in the CAM memory space) and returns a data value (data word) upon detecting a valid match condition for a given key. The CAM contains all keys to be compared during a search operation. In a conventional CAM, each key (i.e., entry) in the CAM is associated with a single data word. The association can be by location, that is, entries in the CAM can map directly to data stored in a RAM. As such, the associative data portion of the CAM can be of the form of an actual data word or a pointer to the data word that is associated with the corresponding key.
In use, a CAM is searched whenever the information associated with a key is needed. A search is performed in the valid portion of the CAM. If a match is detected, a data word associated with the matching key is returned. Where the association is by location, the address of the key is obtained when a match is detected. Using the returned address, data can be read from, for example, a RAM that is used to store the associated data words.
An example of a conventional CAM including associated RAM for storing data words is shown in FIG. 1a. The CAM 100 includes a plurality of entries 102, each including a valid bit 104 and a key 106. The valid bit is set for each valid entry in CAM 100. Not shown, but associated with each entry in the CAM 100, is an address for a given entry. Data words are stored in an external RAM 108. Data words are located in RAM 108 in accordance with the addresses associated with the given entries (keys) in CAM 100. An external search engine 110 provides keys to be searched for in the information space associated with CAM 100. Thereafter, the valid portion of the CAM 100 (all valid entries) is searched. The address of a matching key is obtained upon detection of a match. The address is in turn forwarded to control logic 111. Control logic 111 uses the address to access the appropriate data word stored in the RAM 108 (the data word associated with the key being searched).
Another example of a conventional CAM is shown in FIG. 1b, which is used to make forwarding decisions of packets in a router or switch. Each entry 102 in CAM 150 can include a tag 112. The tag 112 is used to designate the entry as being either a source address or destination address. Accordingly, the same key can be stored multiple times in CAM 150 as a source address and as a destination address. Depending on whether the search invoked by search engine 110 is for a destination address or source address, different hits will result in CAM 150 for the same key. The number of entries or blocks in CAM 150 is equal to the sum of the number of source addresses and destination addresses that are to be searched.
CAM memory tends to be expensive (relative to RAM). As the information base associated with a CAM grows, such as when multiple copies of the same key are included in the CAM, costs rise. What is desired is a means to be able to minimize the CAM size while still realizing the benefits derived from an associative memory structure.
In one aspect, the invention provides a content addressable memory including an associative memory portion including N entries, each entry including a key. The content addressable memory further includes a random access memory portion. The random access memory portion includes K*N entries where a single key stored as an entry in the associative memory portion is mapped to K entries in the random access memory portion, where K is greater than 1.
Aspects of the invention can include one or more of the following features. Each entry in the random access memory portion can be associated with a single key and can include information based on the key type. The type can be a source or destination address. The type can be a MAC address or an MPLS label. Each entry can include an M-bit type indicator, where M is greater than 1. The number of types can be two, source and destination addresses. The content addressable memory can be configured such that K=M.
In another aspect the invention provides a content addressable memory including an associative memory portion including N entries, each entry including a key and an M-bit type indicator, where M is greater than 1. The content addressable memory further includes a random access memory portion. The random access memory portion includes N entries including K portions where a single key stored as an entry in the associative memory portion is mapped to a single entry in the random access memory including the K portions, where K is greater than 1.
In another aspect, the invention provides a content addressable memory for storing MAC addresses and MPLS labels and includes an associative memory portion including N entries. Each entry includes a key and an M-bit type indicator, where M is greater than 1. Each key is of the form of a MAC address or MPLS label or both as indicated by the type indicator. The content addressable memory further includes a random access memory portion. The random access memory portion including K*N entries where a single key stored as an entry in the associative memory portion is mapped to up to K entries in the random access memory portion, where K is greater than 1.
In another aspect, the invention provides a method for storing MAC addresses in a content addressable memory. The content addressable memory includes an associative portion and a random access portion. The associative portion includes one or more entries each including an address. The random access portion is operable to store information relevant to each address. The method includes associating a single address with plural entries in the random access memory when the single address is maintained in the associative portion of the content addressable memory for two different contexts, one dependent on whether the address is a source address and one dependent on whether the address is a destination address.
In another aspect, the invention provides a method for storing MAC addresses in a content addressable memory. The content addressable memory includes an associative portion and a random access portion. The associative portion includes one or more entries each including an address. The random access portion is operable to store information relevant to each address. The method includes determining if an address is present in the associative portion for a first context, either as a source address or destination address. If the address is present, marking the address in the associative portion to indicate that the address is to be associated with a second context. Information relevant to the second context and associated with the address is added to the random access portion including mapping the address to relevant information stored in the random access portion associated with the first context and the second context.
In another aspect, the invention provides a method for storing MAC addresses and MPLS labels in a content addressable memory. The method includes determining if a key is present in a first entry in the associative portion for a first context, either as a source address or destination address or both. If so, a portion of the key to be associated with an MPLS label is located. A same portion for all other keys in the content addressable memory is checked to see if the portion matches. If not, the address in the associative portion of the first entry is marked to indicate that the address is to be associated with a second context, the second context being an MPLS label. Information relevant to the second context and associated with the address is added to the random access portion including mapping the address to relevant information stored in the random access portion associated with the first context and the second context.
Aspects of the invention can include one or more of the following features. If the portion matches, a second portion of the key to be associated with a second MPLS label is located. A same portion for all other keys in the content addressable memory is checked to see if the second portion matches. If not, the address in the associative portion is marked to indicate that the address is to be associated with a second context, the second context being an MPLS label. Information relevant to the second context and associated with the address is added to the random access portion including mapping the address to relevant information stored in the random access portion associated with the first context and the second context.
Aspects of the invention can include one or more of the following advantages. An optimized CAM is proposed that minimizes the CAM portion of a device at the expense of an external RAM portion of the device. The RAM portion of the device associated with the optimized CAM can be scaled up to accommodate a larger information base while keeping the associated CAM portion of the device the same size or smaller. The optimized CAM can include multi-use elements. The multi-use elements allow the optimized CAM to exploit the whole of the information base to be stored and searched while minimizing the number of entries required to support such operations. The optimized CAM provides a means to combine the search space for the information base to include both Ethernet MAC addresses and MPLS labels. The optimized CAM provides silicon area saving as well as saving in search time with respect to conventional CAM solutions for the same size of search information base. The optimized CAM enables supporting a mix of Ethernet type and MPLS type packets in the same network. One application of the optimized CAM is to implement a resilient packet ring media access controller (MAC). A resilient packet ring MAC provides functionality to allow spatial reuse of bandwidth and resiliency in a ring-based media. The resilient packet ring MAC can operate with Ethernet/802.3 and MPLS packets.
The details of one or more embodiments of the invention are set forth in the accompanying drawings and the description below. Other features, objects, and advantages of the invention will be apparent from the description and drawings, and from the claims.